\chapter{Лекция 7. Контекстно-свободные грамматики и языки. Продолжение}

\section{Бесконечность КС-языков. Финальные соображения}

Используя лемму о накачке легко понять, что если в языке существует слово длинны $>n$, то язык бесконечен, как определить, что такое слово существует? Достаточно
на самом деле проверять слова длинны от $n$ до $2n$, если таких слов нет, то и слов большей длинны не будет. На самом деле суть в том, что любое достаточно длинное
слово уже накачано, то есть мы его можем сдуть взяв в лемме параметр $i = 0$. И так сдувать строку мы гарантированно можем пока она не станет длинны $<2n$. Т. е.
мы доказали, что если язык бесконечен, то он имеет слово длинны от $(n, 2n]$, и наоборот, если язык имеет слово длинны $> n$, то он бесконечен.

\section{Самовставленность}

Пусть $L$ - бесконечный КС-язык, тогда существует КС-грамматика, такая что из любого ее нетерминала выводится бесконечное число слов.

\begin{Def}
$G$ - КС грамматика. Нетерминал $A$ называется самовставленным, если $A \Rightarrow^{*} uAv$, где $u,v \in \left(T \cup N\right)^{+}$.
\end{Def}

\begin{Def}
Грамматика называется самовставленной, если в ней существует самовставленный нетерминал
\end{Def}

\begin{Def}
КС-язык $L$ называется самовстваленным, тогда когда любая порождающая его грамматика самовставленна.
\end{Def}

\section{Преобразования сохраняющие самовставленность}

Приведение к бинарной форме (см. нормальную форму Хомского). Такое преобразование не меняет вывода (т. е. если в исходной грамматике был некоторый вывод, то в новой
его легко восстановить), более того, мы не удаляем нетерминалов исходной грамматики, а только добавляем новые, таким образом, если исходная грамматика самовставленна,
то и новая грамматика тоже будет самовставленной. Покажем теперь обратное, что если новая грамматика самовставленна, то и исходная была самовставленной.

Пусть у нас добавился некоторый новый нетерминал $N$ и он оказался самовставленным, рассмотрим пример: $A ::= BCE$ была преобразована в $A ::= BN$ и $N ::= CE$, таким
образом в нашем примере существует вывод $N \Rightarrow^{*} uNv$. Значит существует вывод в исходной грамматике $A ::= BCE \Rightarrow^{*} BuNv = BuCEv$, а значит
символы $C$ и $E$ самовставленны, т. е. и исходная грамматика также самовставленна.

Устранение цепных правил также не меняет самовставленность, что совсем очевидно.

Устарение левой рекурсии - очень полезное преобразование. Правило вида $A ::= Aw$ называется леворекурсивной, кроме того существует неявная левая рекурсия
$A \Rightarrow^{*} Aw$.

\section{Нормальная форма Грейбах}

\begin{Def}
КС-грамматика находится в нормальной форме Грейбах тогда и только тогда, когда все ее правила имеют форму $A ::= xu$, где $X \in T$, а $u \in N^{*}$
\end{Def}

Любую КС-грамматику можно привести к нормальной форме Грейбах.

Порядок приведения:

\begin{enumerate}
\item Приводим грамматику к нормальной форме Хомского

\item Упорядочим все нетерминалы в грамматике (т. е. пронумеруем их)

\item Если правая часть правила начинается с нетерминала, номер которого меньше чем норме нетерминала в левой части, то преобразуем правило, по следующему примеру:
рассмотрим все правила для $A_1$, они либо имееют нужную форму или имеют левую рекурсию, если имеют левую рекурсию то устраним ее и перейдем к следующему по порядку
нетерминалу. Если у очередного нетерминала присутствуют правила, правая часть которых начинаяется с нетерминала с меньшим нормером, подставим вместо этого неправильного
нетерминала его правила, пока не приведем его к нужной форме или не получим левую рекурсию, которую мы благополучно удаляем. Заметим, что при удалении левой рекурсии
у нас появляются новые нетерминалы, мы их не нумеруем и не рассматриваем. После того, как мы доберемся до конечного нетерминала, все его правила в правой части содержат
толькотерминалы и легко преобразуются к нужному виду, после преобразования делаем обратный ход, раскрывая правила начинающиеся с нетерминала подстановкой правила
для этого нетерминала, так как он имеет больший номер, подстановка приведет правимло к нужному виду.
\end{enumerate}

Приведение к нормальной форме Грейбах сохраняет самовставленность и это важно и вот почему. Пусть $G$ - несамовставленная грамматика в нормальной форме Грейбах.
Тогда если выводя строку заменяя каждый раз самый левый нетерминал, получаем вывод $S \Rightarrow w_1 \Rightarrow ... \Rightarrow w_2 ...$. Каждый $w_i$ всегда
начинается с терминала, более того имеет вид $w_i = \alpha_i u_i$, где $\alpha_i \in T^{+}$ и $u_i \in N^{*}$. Пусть $l$ - длинна самого длинного нетерминального
хвоста по всем правилам, тогда после применения $k$ правил вывода, нетерминальный хвост будет не больше чем $kl$. Пусть в нашей грамматике $m$ нетерминалов и на
каком-то шаге мы получили нетерминальный хвост длинны $(m + 1)l$, значит в дереве вывода какой-то нетерминал встретился как минимум 2 раза, а значит в грамматике
есть самовставленный нетерминал, что противоречит условию несамовставленности, а значит для любой несамовставленной грамматики такой хвост всегда ограничен конечным
числом, и этот факт позволит построить нам автомат допускающий данную цепочку, т. е. язык является регулярным.

Построим регулярную грамматику по несамовставленной грамматике в нормальной форме Грейбах. Для этого каждой строке из нетерминалов длинны не более $ml$ сопоставляем
свой собственный нетерминал. Начальный нетерминал новой грамматики является нетерминал соответсвующий одному стартовому символу исходной грамматики. Правила для
такого множества нетерминалов получаются вполне очевидным образом, для этого возьмем нетерминал $A$ новой грамматики, пусть соответсвующая ему строка нетерминалов
исходной грамматики выглядит как $A'w$, где $A'$ - нетерминал исходной грамматики, рассмотрим все правила исходной грамматики для нетерминала $A'$ и каждому такому
 правилу вида $A' ::= cC$ сопоставим правило $A ::= c[Cw]$, где $[Cw]$ - нетерминал новой грамматики соответсвующий строке нетерминалов $Cw$, а каждому правилу
 вида $A' ::= c$ сопоставляем правило $A ::= c[w]$.
 
\section{Алгоритм Эрли для разбора КС-языка по грамматике}

Мы рассмотрим алгоритм приметильно к грамматикам без $\varepsilon$-правил и без заглядывания вперед, других ограничений на грамматику не будет.

Пусть $G$ - КС-грамматика и $w$ - входное слово длинны $n$. Строим вектор "множеств Эрли" $\lbrace S_i\rbrace^{n}_{i=0}$. К грамматике нужно добавить нетерминал $S'$
и правило вывода $S' ::= S$.

Множество Эрли - множество пар вида: правило грамматики, в котором в правой части отмеченая текущая позиция, и второй элемент - номер символа в $w$, в котором началось
применение данного правила. Стартовое множество эрли состоит из всего одной пары $\lbrace S' ::= *S, 0\rbrace$.
Для получения новго множества Эрли используются три преобразования:

\begin{enumerate}
\item Scanner. Смотрим на текущую позицию во входной строке (для позиций $i > 0$, т. е. начальный символ строки пропускается). $S_{i-1}$ - множество Эрли
аолученное на предыдущем шаге. Выбираем все элементы из $S_{i-1}$ у которых метки стоят перед символом $w[i]$ (т. е. рассматриваем только правила, в которых метка стоит
перед терминалом). В новое множество Эрли добавляем все эти правила, переместив метку на один символ вперед, а начальную позицию пары оставляем неизменной.

\item Predictor. В этом преобразовании мы рассматриваем только те правила, в которых метка стоит перед нетерминалом. В $S_i$ добавляем все правила исходной грамматики
для помеченного нетерминала, и добавляем пары пометив начальные символы правых частей правила и указав стартовым символ $i$.

\item Compliter. Ищем все пары вида $(A ::= ...*, j)$, и для каждой такой пары ищем в $S_j$ пары вида $(... ::= ...*A..., k)$ и для каждой такой пары добавляем
в $S_i$ элементы вида $... ::= ..A*..., k$.
\end{enumerate}

Если строка заматчена, то в конечном множестве должно присутствовать правило вида $S' : S*$.
